package algorithm.sort;

import java.util.Arrays;

/**
 * 希尔排序
 *
 * @author hck
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
//        System.out.println("source:" + Arrays.toString(array));
        System.out.println(Arrays.toString(array));
        sort(array);
        System.out.println("sorted:" + Arrays.toString(array));
    }


    /**
     * 希尔排序
     */
    public static void sort(int array[]) {
        int group = array.length;
        int shellCount = 0;
        int groupCount = 0;
        for (group /= 2; group >= 1; group /= 2) {
            //  遍历每一个组
            for (int i = group; i < array.length; i++) {
                groupCount++;
                for (int j = i - group; j >= 0; j -= group) {
                    if (array[j + group] < array[j]) {
                        SortUtil.swap(array, j, j + group);
                    }
                    System.out.println(Arrays.toString(array));
                    System.out.println("-----------------------------");
                }
            }


//            System.out.println("第" + (++shellCount) + "轮 group:" + group + " array:" + Arrays.toString(array));
//            System.out.println("遍历了" + groupCount + "组");
//            System.out.println("shell deal:" + Arrays.toString(array));
        }
    }

    public static void shellSort(int[] arr) {
        int length = arr.length;
        int temp;
        for (int step = length / 2; step >= 1; step /= 2) {
            for (int i = step; i < length; i++) {
                temp = arr[i];
                int j = i - step;
                while (j >= 0 && arr[j] > temp) {
                    arr[j + step] = arr[j];
                    j -= step;
                }
                arr[j + step] = temp;
            }
        }
    }

}
